// 题目描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
// 左括号必须用相同类型的右括号闭合。
// 左括号必须以正确的顺序闭合。
// 注意空字符串可被认为是有效字符串。


const map = new Map([
    ['{', '}'],
    ['(', ')'],
    ['[', ']']
])
/**
 * 括号总是成对出现的 并且是有顺序的
 * 匹配到左括号的时候 将对应的右括号入栈
 * 当左括号匹配结束 开始匹配字符串中的右括号的时候栈顶的元素应该与前一个字符匹配
 * 每匹配成功一个弹出，不匹配则字符串不满足题目
 * 当栈空的时候说明字符串满足题目要求
 *
 */
const valid = (str) => {
    // 空字符串则返回true
    if(!str) {
        return true
    }
    // 开辟一个栈空间
    const arr = []
    // 遍历字符串
    for(let i = 0; i < str.length; i++) {
        let ch = str[i]
        if(ch === '(' || ch === '[' || ch === '{') {
            // 当匹配到左括号的时候将对应的右括号入栈
            arr.push(map.get(ch))
        } else {
            // 如果栈不为空并且 栈顶的左括号没有和当前字符匹配则判为无效
            if (arr.length && arr.pop() !== ch) {
                return false
            }
        }
    }
    return !arr.length
}
